package day20210628;

import treenode.SimpleTreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 257. 二叉树的所有路径
 * 最直观的方法是使用深度优先搜索。在深度优先搜索遍历二叉树时，我们需要考虑当前的节点以及它的孩子节点。
 *
 * 如果当前节点不是叶子节点，则在当前的路径末尾添加该节点，并继续递归遍历该节点的每一个孩子节点。
 * 如果当前节点是叶子节点，则在当前路径末尾添加该节点后我们就得到了一条从根节点到叶子节点的路径，将该路径加入到答案即可。
 *
 * 作者：LeetCode-Solution
 * 链接：https://leetcode-cn.com/problems/binary-tree-paths/solution/er-cha-shu-de-suo-you-lu-jing-by-leetcode-solution/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 * @author lizy4
 * @date 2021/6/28 11:28
 */
class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        SimpleTreeNode simpleTreeNode = new SimpleTreeNode();
        simpleTreeNode.val = 6;
        simpleTreeNode.right = new SimpleTreeNode(8);
        simpleTreeNode.right.right = new SimpleTreeNode(9);
        simpleTreeNode.right.left = new SimpleTreeNode(7);
        simpleTreeNode.left = new SimpleTreeNode(2);
        System.out.println(solution.binaryTreePaths(simpleTreeNode));
    }

    private List<String> binaryTreePaths(SimpleTreeNode root) {
        List<String> paths = new ArrayList<>();
        constructPaths(root, "", paths);
        return paths;
    }

    private void constructPaths(SimpleTreeNode root, String path, List<String> paths) {
        if (root != null) {
            StringBuffer pathSB = new StringBuffer(path);
            pathSB.append(root.val);
            // 当前节点是叶子节点
            if (root.left == null && root.right == null) {
                // 把路径加入到答案中
                paths.add(pathSB.toString());
            } else {
                // 当前节点不是叶子节点，继续递归遍历
                pathSB.append("->");
                constructPaths(root.left, pathSB.toString(), paths);
                constructPaths(root.right, pathSB.toString(), paths);
            }
        }
    }
}